<?php

/**
 * 原理：基于插入排序的改造，减少了比较次数。①计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；②在相应的半个范围里面找插入的位置时，不断的用①步骤缩小范围，不停的折半，范围依次缩小为 1/2 4 8 .......快速的确定出第 i  个元素要插在什么地方；③确定位置之后，将整个序列后移，并将元素插入到相应位置。
 *
 * 比较：折半比直接排序明显比较次数会减少很多，但是移动的次数没有改变的。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2）。
 */
class 折半插入排序
{
    public function 运行($输入数组)
    {
        $数组长度 = count($输入数组);

        if ($数组长度 <= 1) {
            return $输入数组;
        }

        $待插入数 = 0;
        for ($i = 1; $i < $数组长度; $i++) { 
            $待插入数 = $输入数组[$i];
            $低位 = 0;
            $高位 = $i - 1;

            while ($低位 <= $高位) {
                $中间位 = floor(($低位 + $高位) / 2);
                if ($输入数组[$中间位] < $待插入数) {
                    $低位 = $中间位 + 1;
                } else {
                    $高位 = $中间位 - 1;
                }
            }

            // 当找到了要插入的点之后，就是需要让自插入点之后的数组统一后移一位
            for ($j = $i; $j > $低位; $j--) { 
                $输入数组[$j] = $输入数组[$j - 1];
            }
            $输入数组[$低位] = $待插入数;
        }

        return $输入数组;
    }
}

$输入数组 = [5, 9, 6, 3, 1, 4];
$实例 = new 折半插入排序();

$结果数组 = $实例->运行($输入数组);

print_r($结果数组);